package main

func partition(nums []int, left, right int) int {
	p := nums[left] // 先把这个值存起来,这个位置就当做"坑"
	i, j := left, right
	// 左区间[left,i]<=p   右区间[j,right]>=p
	// 左右两边延伸,同时找到不合理的值, 交换
	for i < j {
		// 假设一轮交换后,i先走,则i与j会在>pivot值的位置相遇
		// 而j先走,则i与j会在<pivot值的位置相遇   =>  才满足把p交换过来时,该位置及以前的所有元素都<=>pivot值
		// 故此处需要j先走
		for i < j && nums[j] >= p {
			j--
		}
		for i < j && nums[i] <= p {
			i++
		}
		// 交换
		nums[i], nums[j] = nums[j], nums[i]
	}
	// 当前循环完成后, i和j相遇的位置就是 小值区间 与 大值区间交界处  且 交界位置值是属于小值区间

	// 但交界值只能保证是 <= pivot值, 不能保证是 = pivot值 ,   故直接把属于小值区间的第一个值[pivot值]交换到交界处 当做隔离即可
	nums[left], nums[i] = nums[i], nums[left]
	return i
}

func QuickSortCore(nums []int, left, right int) {
	if len(nums) <= 1 {
		return
	}
	pivot := partition(nums, left, right)

	partition(nums, left, pivot-1)
	partition(nums, pivot+1, right)
}
func QuickSort(nums []int) {
	QuickSortCore(nums, 0, len(nums)-1)
}
